

package algo

func max_profit(price []int)  int{
	// 为了迭代不越界，从1天开始
	// f[n] = max(f[n-1], p[n] - min(p[n-1],...)
	// g[n] = min(price[n])
	if len(price) < 2{
		return 0
	}
	n :=len(price)
	f := make([]int,n+1)
	g :=make([]int, n+1)
	// g--p
	g[1] = price[0]
	for i:=2;i<=n;i++{
		if f[i-1] >=  price[i-1]-g[i-1]{
			f[i] = f[i-1]
		}
		if (price[i-1] < g[i-1]){
			g[i] = price[i-1]
		}
	}
	return f[n]
}